﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;

namespace Activity.I
{
	/// <summary>
	/// Демонстрационная программа 1-ой лабораторной работы
	/// </summary>
	public class Program
	{
		public const int MinSize = 100; //		Минимальный размер массива
		public const int MaxSize = 1000; //		Максимальный размер массива
		public static Array buffer; //			Массив

		/// <summary>
		/// Начало программы.
		/// </summary>
		public static void Main ()
		{
			Console.BufferHeight = MaxSize + 100;
			Console.OutputEncoding = Encoding.Unicode;
			buffer = new int[new Random().Next(MinSize, MaxSize)];
			Fill(buffer);
			DisplayMenu(MenuEntry.Main);
		}

		/// <summary>
		/// Отобразить указанное меню.
		/// </summary>
		/// <param name="menu">Числовое представление активного меню.</param>
		public static void DisplayMenu (MenuEntry menu)
		{
			Console.Clear();
			Console.WriteLine("Лабораторная работа #1 [Вариант #5]");
			Console.WriteLine("Тема: \"Поиск ключа в массиве. Анализ эффективности алгоритмов поиска\"\n");
			// Переходим к следующему меню
			switch (menu)
			{
				case MenuEntry.Main:
					MainMenu();
					break;
				case MenuEntry.Create:
					CreateArrayMenu();
					break;
				case MenuEntry.Fill:
					FillArrayMenu();
					break;
				case MenuEntry.Display:
					PrintArrayMenu();
					break;
				case MenuEntry.Sort:
					SortArrayMenu();
					break;
				case MenuEntry.Search:
					SearchArrayMenu();
					break;
				case MenuEntry.Exit:
					// Не переходим к следующему меню
					return;
			}
		}

		/// <summary>
		/// Отобразить главное меню.
		/// </summary>
		private static void MainMenu ()
		{
			// Текст меню
			Console.WriteLine("Главное Меню");
			Console.WriteLine();
			Console.WriteLine("1. Создать массив");
			Console.WriteLine("2. Заполнить массив");
			Console.WriteLine("3. Показать массив");
			Console.WriteLine("4. Сортировка массива");
			Console.WriteLine("5. Бинарный поиск");
			Console.WriteLine("0. Выход");
			Console.WriteLine();

			// Выбор меню
			var option = ReadInt("Выбор[0-5]: ");
			DisplayMenu(GetMainMenuEntry(option));
		}

		/// <summary>
		/// Преобразовать выбор пользователя в численное представление меню.
		/// </summary>
		/// <param name="option">Значение выбранное пользователем.</param>
		/// <returns>Меню которое необходимо показать.</returns>
		private static MenuEntry GetMainMenuEntry (int option)
		{
			switch (option)
			{
				case 1:
					return MenuEntry.Create;
				case 2:
					return MenuEntry.Fill;
				case 3:
					return MenuEntry.Display;
				case 4:
					return MenuEntry.Sort;
				case 5:
					return MenuEntry.Search;
				case 0:
					return MenuEntry.Exit;
				default:
					return MenuEntry.Main;
			}
		}

		/// <summary>
		/// Отобразить меню создания массива.
		/// </summary>
		private static void CreateArrayMenu ()
		{
			Console.WriteLine("Создание Массива\n");

			int size;
			bool hasValidSize;
			do
			{
				// Считываем размер массива до тех пор пока не будет удовлетворять условиям
				size = ReadInt(String.Format("Введите размера массива [{0} - {1}]: ", MinSize, MaxSize));
				hasValidSize = size >= MinSize && size <= MaxSize;
				if (!hasValidSize) Console.WriteLine("Неверный размер массива!\n");
			} while (!hasValidSize);

			// Создаем и заполняем массив
			buffer = new int[size];
			Fill(buffer);

			// Отображаем элементы массива
			Console.WriteLine();
			Print(buffer);

			ReadLine("\nНажмите клавишу ввода для возврата в главное меню...");
			DisplayMenu(MenuEntry.Main);
		}

		/// <summary>
		/// Отобразить меню заполнения массива.
		/// </summary>
		private static void FillArrayMenu ()
		{
			Console.WriteLine("Заполнение Массива\n");

			// Заполняем и отображаем элементы массива
			Fill(buffer);
			Print(buffer);

			ReadLine("\nНажмите клавишу ввода для возврата в главное меню...");
			DisplayMenu(MenuEntry.Main);
		}

		/// <summary>
		/// Отобразить меню вывода массива.
		/// </summary>
		private static void PrintArrayMenu ()
		{
			Console.WriteLine("Вывод Массива\n");

			// Отображаем элементы массива
			Print(buffer);
			ReadLine("\nНажмите клавишу ввода для возврата в главное меню...");
			DisplayMenu(MenuEntry.Main);
		}

		/// <summary>
		/// Отобразить меню сортировки.
		/// </summary>
		private static void SortArrayMenu ()
		{
			Console.WriteLine("Сортировка Массива\n");

			// Засекаем время необходимое на сортировку массива
			var watch = Stopwatch.StartNew();
			Sort(buffer, Comparer<int>.Default);
			watch.Stop();

			// Отображаем элементы массива
			Print(buffer);
			Console.WriteLine("\nОперация сортировки заняла {0} тактов системного таймера.", watch.ElapsedTicks);

			ReadLine("\nНажмите клавишу ввода для возврата в главное меню...");
			DisplayMenu(MenuEntry.Main);
		}

		/// <summary>
		/// Отобразить меню поиска элемента в массиве.
		/// </summary>
		private static void SearchArrayMenu ()
		{
			Console.WriteLine("Бинарный Поиск Элемента\n");

			var value = ReadInt("Введите целочисленное значение для поиска: ");
			var watch = Stopwatch.StartNew();
			var index = Find(buffer, value);
			watch.Stop();

			Console.WriteLine();
			if (index >= 0) Console.WriteLine("Элемент {0} найден по индексу {1}.", value, index);
			else Console.WriteLine("Элемент {0} не найден.", value);
			Console.WriteLine("Операция бинарного поиска заняла {0} тактов системного таймера.", watch.ElapsedTicks);

			ReadLine("\nНажмите клавишу ввода для возврата в главное меню...");
			DisplayMenu(MenuEntry.Main);
		}

		#region Операции над массивом
		/// <summary>
		/// Заполнить массив случайными целыми числами.
		/// </summary>
		public static void Fill (IList array)
		{
			var random = new Random();
			for (int i = 0; i < array.Count; i++)
				array[i] = random.Next(0, array.Count);
		}

		/// <summary>
		/// Линейный поиск указанного элемента в массиве.
		/// </summary>
		/// <param name="array">Экземпляр массива.</param>
		/// <param name="value">Значение которое необходимо найти.</param>
		/// <returns>Индекс элемента если был найден; в противном случае -1.</returns>
		public static int Find (IList array, object value)
		{
			for (int i = 0; i < array.Count; i++)
				if (Equals(array[i], value))
					return i;
			return -1;
		}

		/// <summary>
		/// Бинарный поиск указанного элемента в массиве.
		/// </summary>
		/// <param name="array">Экземпляр массива.</param>
		/// <param name="value">Значение которое необходимо найти.</param>
		/// <param name="comparer">Алгоритм сравнения элементов массива.</param>
		/// <returns>Индекс элемента если был найден; в противном случае -1.</returns>
		public static int BinarySearch (IList array, object value, IComparer comparer)
		{
			return BinarySearch(array, value, comparer, 0, array.Count);
		}

		/// <summary>
		/// Бинарный поиск указанного элемента в массиве.
		/// </summary>
		/// <param name="array">Экземпляр массива.</param>
		/// <param name="value">Значение которое необходимо найти.</param>
		/// <param name="comparer">Алгоритм сравнения элементов массива.</param>
		/// <param name="bottom">Нижняя граница поиска.</param>
		/// <param name="top">Верхняя граница поиска.</param>
		/// <returns>Индекс элемента если был найден; в противном случае -1.</returns>
		public static int BinarySearch (IList array, object value, IComparer comparer, int bottom, int top)
		{
			if (top < bottom) return -1;
			var index = (bottom + top) / 2;
			var compare = comparer.Compare(value, array[index]);

			if (compare < 0) return BinarySearch(array, value, comparer, bottom, index - 1); // value < array[i]
			if (compare > 0) return BinarySearch(array, value, comparer, index + 1, top); // value > array[i]
			return index; // value == array[i]
		}

		/// <summary>
		/// Пузырьковая сортировка массива.
		/// </summary>
		/// <param name="array">Экземпляр массива.</param>
		/// <param name="comparer">Алгоритм сравнения элементов массива.</param>
		public static void Sort (IList array, IComparer comparer)
		{
			for (int i = 0; i < array.Count; i++)
				for (int j = i + 1; j < array.Count; j++)
				{
					var compare = comparer.Compare(array[i], array[j]);
					if (compare > 0) Swap(array, i, j);
				}
		}

		/// <summary>
		/// Обмен элементов массива.
		/// </summary>
		/// <param name="array">Экземпляр массива.</param>
		/// <param name="x">Индекс элемента для обмена.</param>
		/// <param name="y">Индекс элемента для обмена.</param>
		public static void Swap (IList array, int x, int y)
		{
			if (x == y) return;
			var t = array[x];
			array[x] = array[y];
			array[y] = t;
		}

		/// <summary>
		/// Вывод элементов массива на экран.
		/// </summary>
		/// <param name="array">Экземпляр массива.</param>
		public static void Print (IList array)
		{
			Console.WriteLine("Элементы списка [{0}]:", array.Count);
			for (int i = 0; i < array.Count; i++)
				Console.WriteLine("[{0}] = {1}", i, array[i]);
		}

		#endregion

		/// <summary>
		/// Считать данные введенные пользователем.
		/// </summary>
		/// <param name="message">Приглашение для ввода данных.</param>
		/// <returns>Возвращает текст введенный пользователем.</returns>
		private static string ReadLine(string message)
		{
			Console.Write(message);
			return Console.ReadLine();
		}

		/// <summary>
		/// Считать целое число введенное пользователем.
		/// </summary>
		/// <param name="message">Приглашение для ввода данных.</param>
		/// <returns>Возвращает целое число которое ввел пользователь; в противном случае -1.</returns>
		private static int ReadInt(string message)
		{
			Console.Write(message);
			int retVal;
			if (Int32.TryParse(Console.ReadLine(), out retVal))
				return retVal;
			return -1;
		}

		/// <summary>
		/// Перечисление возможных меню для отображения.
		/// </summary>
		public enum MenuEntry
		{
			Main,
			Exit,
			Create,
			Fill,
			Display,
			Sort,
			Search
		}
	}
}
